perm filename FINAL.S78[206,LSP] blob
sn#361411 filedate 1978-06-15 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00009 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 .REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file
C00004 00003 .hd206 Spring 1978
C00005 00004 [20 points]#. Imagine that you are writing a program to play card games. This
C00011 00005 [15 points]#. The function mirror[x] computes the "mirror image" of an S-expression.
C00014 00006 [15 points]#. This problem concerns iteration of functions and sequences of statements.
C00017 00007 [15 points]#. The following is a sequential program to compute the predicate perf.
C00019 00008 [25 points]#. Let po be a list of pairs of atoms. po defines an ordering relation
C00027 00009 [25 points]#. Add a clause qif qa exp = $WHILE qthen ... to compexp in LCOM0
C00032 ENDMK
C⊗;
.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file;
.
.MACRO hd206 (TERM) ⊂
.BEGIN NOFILL TURNON "←→"
.place heading
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY
.place text
CS206 ←COMPUTING WITH SYMBOLIC EXPRESSIONS →TERM
.TURNOFF
.END ⊃
.LSPFONT
.FONT A "FIX25";
.basicops
.allops
.itemmac 1
.PORTION MAINPORTION
.PAGE ← 1
.hd206 Spring 1978
.cb Final Exam and Solutions.
.skip
This examination is open book and notes.
When you are asked to write LISP programs you may use external or internal form.
Read each question carefully and be sure you understand what is wanted before you
begin work. Do problems 1 through 4 and either 5 or 6. There is a total of
90 points possible distributed as indicated at the beginning of each problem.
GOOD LUCK!!
.item←0
[20 points]#. Imagine that you are writing a program to play card games. This
question concerns some of the problems you might have to solve in writing
such a program.
.begin indent 4,4
##. Decide on a representation of a playing card as an S-expression.
Each card will have a ⊗suit [$HEART, $DIAMOND, $CLUB, or $$SPADE$]
and a ⊗value [$2, ... $10, $J, $Q, $K or $$A$]. Write a predicate
⊗iscard[x] that determines if an arbitrary S-expression represents a
card. Write functions ⊗suit and ⊗value that return the corresponding
properties when given an S-expression satisfying ⊗iscard.
The obvious representation is a pair $$(<suit>.<value>)$ although
a two element list would work also. We define two global constants:
.begin nofill
⊗⊗ suits ← $$(CLUB DIAMOND HEART SPADE)$⊗
⊗⊗ values ← $$(2 3 4 5 6 7 8 9 10 J Q K A)$⊗
then
⊗⊗ iscard x ← ¬qat x ∧ memq[qa x, suits] ∧ memq[qd x, values]⊗
⊗⊗ suitof x ← qa x⊗
⊗⊗ value x ← qd x⊗
.end
##. Write a program ⊗makdek which takes no arguments and returns a list
containing the 52 cards of a deck. (Any order will do).
.begin nofill
⊗⊗ makdek[] ← ⊗
⊗⊗ mapapp[[λs: mpacar[[λval: s . val], values]], suits]⊗
where
⊗⊗ mapapp[f, u] ← qif qn u qthen qNIL qelse apply[f, <qa u>] * mapapp[f, qd u]⊗
.end
##. Write a program which takes as input a list of cards (a hand) and
returns a list consisting of the maximal runs of length ≥ 3 in the hand.
A run is a list of cards satisfying ⊗isrun where
⊗next[val] is simply the next item in the list of values given above and
⊗⊗⊗isrun u ← qn u ∨ qn qd u ∨ [[suit qa u=suit qad u] ∧ [value qad u=next value qa u]
∧ [isrun qd u]]⊗.
A maximal run is one that cannot be extended in either direction by the cards
remaining in the hand. The initial order of cards in the hand is unimportant.
The idea is to extract runs from the hand by starting with the next
card left, figuring out what card extends the run downward if any using ⊗before
and if it is in the hand moving it to the run being built. When this can
no longer be done the run is extended upward using ⊗after to find the next
card in the run. When the run is maixmally extended, it is either discarded
if the length is less than 3 or added to the result. Then the process is
continued until the hand is empty.
.begin nofill
⊗⊗ mkruns h ← qif qn h qthen qNIL qelse lrun[qd h, <qa h>]⊗
⊗⊗ lrun[h, run] ← ⊗
⊗⊗ {before qa run}[λc: ⊗
⊗⊗ qif c ε h qthen lrun[del[c, h], c . run] qelse rrun[h, run]]⊗
⊗⊗ rrun[h, run] ← ⊗
⊗⊗ {after lastof run}[λc: ⊗
⊗⊗ qif c ε h qthen rrun[del[c, h], run * <c>]⊗
⊗⊗ qelse qif length run < 3 qthen mkruns h⊗
⊗⊗ qelse run . mkruns h]⊗
where
⊗⊗ next[x, v] ← ⊗
⊗⊗ qif qn qd v qthen qNIL qelse qif x = qa v qthen qad v qelse next[x, qd v]⊗
⊗⊗ before c ← suitof c . next[value c, reverse values]⊗
⊗⊗ after c ← suitof c . next[value c, values]⊗
⊗⊗ lastof u ← qif qn qd u qthen qa u qelse lastof qd u⊗
⊗⊗ del[x, u] ← ⊗
⊗⊗ qif qn u qthen qNIL qelse qif x = qa u qthen qd u qelse qa u . del[x, qd u]⊗
.end
.end
[15 points]#. The function ⊗mirror[x] computes the "mirror image" of an S-expression.
It is defined by
⊗⊗⊗mirror[x] ← qif qat x qthen x qelse [mirror qd x] . [mirror qa x]⊗.
Prove the following statements:
.begin indent 4,4
##. ⊗⊗∀x: issexp mirror x⊗
This is done by S-expression induction. In the case ⊗⊗qat x⊗,
⊗⊗mirror_x_=_x⊗ and we have ⊗issexp_x. In the case ⊗⊗¬qat x⊗ ⊗⊗mirror_x⊗ is
⊗⊗mirror_qd x_._mirror_qa x⊗. By induction both arguments to ⊗cons satisfy
⊗issexp and by the LISP axioms the result of the ⊗cons satisfies ⊗issexp. Thus
the proof is complete.
##. ⊗⊗∀x: [fringe mirror x = reverse fringe x]⊗
.begin nofill turnon "∂"
.n←50
Again we use S-expression induction. In the case ⊗⊗qat x⊗ we have
⊗⊗fringe mirror x = fringe x⊗ ∂(n)by definition of ⊗mirror
⊗⊗ = <x>⊗ ∂(n)by definition of ⊗fringe
⊗⊗ = reverse <x>⊗∂(n)by definition of ⊗reverse
⊗⊗ = reverse fringe x⊗ ∂(n) by substitution
In the case ⊗⊗¬qat x⊗ we have:
.n ← 60
⊗⊗fringe mirror x = fringe[mirror qd x . mirror qa x]⊗ ∂(n) by definition of ⊗mirror
⊗⊗ = [fringe mirror qd x] * [fringe mirror qa x]⊗ ∂(n)by $FRINGECONS
(since by the above proof and hypothesis that ⊗⊗¬qat x⊗,
⊗⊗mirror_qd x⊗ and ⊗⊗mirror_qa x⊗ are S-expressions.)
⊗⊗ = [reverse fringe qd x] * [reverse fringe qa x]⊗ ∂(n) by induction
⊗⊗ = reverse[[fringe qa x] * [fringe qd x]]⊗ ∂(n) by homework
(since ⊗⊗islist fringe qa x⊗ and ⊗⊗islist fringe qd x⊗)
⊗⊗ = reverse fringe x⊗ ∂(n) by definition of ⊗fringe
.end
.end
[15 points]#. This problem concerns iteration of functions and sequences of statements.
.begin indent 4,4
##. Write a program ⊗repeat[f,n,x] which takes as input a function ⊗f,
a number ⊗n and an initial input ⊗x and returns the result of iterating
⊗f ⊗n times begining with input ⊗x. Thus the value of ⊗repeat[f,0,x] is ⊗x,
the value of ⊗repeat[f,2,x] is ⊗f[f[x]], and so on. As a particular example,
⊗⊗repeat[add1,5,0]⊗ is 5.
.begin nofill
⊗⊗ repeat[f, n, x] ← ⊗
⊗⊗ qif n = 0 qthen x qelse repeat[f, sub1 n, apply[f, <x>]]⊗
.end
##. Write a program ⊗mk-for[var,lo,hi,seq] that takes as input a variable name,
two integers and a sequence of statements [of the sort that can occur in a qprog]
and produces the LISP code which when evaluated will have the effect of
executing the sequence of statements with ⊗var=lo, ⊗var=lo+1, ... ⊗var=hi.
Thus
.begin nofill indent 0,0
⊗⊗mk-for[$$J, 1, 4, ((SETQ F (TIMES F J)))$]=⊗
$$(PROG (J) (SETQ J 1) FOR (SETQ F (TIMES F J)) (SETQ J (ADD1 J)) (COND ((LESSEQ J 4) (GO FOR))))$
and
⊗⊗ mkfor[var, lo, hi, seq] ← ⊗
⊗⊗ [<$$PROG$, <var>, <$$SETQ$, var, lo>, $$FOR$> * seq]⊗
⊗⊗ * <<$$SETQ$, var, <$$ADD1$, var>>, ⊗
⊗⊗ <$$COND$, <<$$LESSEQ$, var, hi>, $$(GO FOR)$>>>⊗
.end
.end
[15 points]#. The following is a sequential program to compute the predicate ⊗perf.
Convert this into a functional program [a program containing no assignments
or qgo's] that computes the same predicate.
.begin nofill select 2 indent 16,16
perf[n] ←
qprog[[x,y,z];
x ← n; y ← n; z ← n;
per1: x ← x-1;
qif x=0 qthen qreturn[z=0];
per2: qif y≥x qthen [y ← y-x; qgo per2];
qif y=0 qthen z ← z-x;
y ← n;
qgo per1]
%1and%*
⊗⊗ perf n ← perf1[n, n, n]⊗
⊗⊗ perf1[x, y, z] ← qif x = 1 qthen z = 0 qelse perf2[sub1 x, y, z]⊗
⊗⊗ perf2[x, y, z] ← ⊗
⊗⊗ qif ¬[x > y] qthen perf2[x, y - x, z]⊗
⊗⊗ qelse qif y = 0 qthen perf1[x, n, z - x]⊗
⊗⊗ qelse perf1[x, n, z]⊗
.end
[25 points]#. Let ⊗po be a list of pairs of atoms. ⊗po defines an ordering relation
on these atoms as follows: if ⊗x.y occurs in ⊗po then ⊗x precedes ⊗y
[written ⊗⊗x_<_y⊗]. Let ⊗s be the list [set] of atoms occuring in ⊗po.
⊗topsort[po] is a list ⊗u such that each element of ⊗s occurs in ⊗u
at most once. Further more, if ⊗⊗x_<_y⊗ in the ordering defined by ⊗po
and ⊗x and ⊗y both occur in ⊗u then ⊗x must occur before ⊗y in ⊗u. Finally, ⊗u
contains all of the elements of ⊗s if possible. In any case ⊗u is "sorted"
with respect to the ordering defined by ⊗po.
Thus if ⊗po is $$((A.D)(B.D)(C.D)(C.A))$ we have $$A_<_D$,
$$B_<_D$, $$C_<_D$, and $$C_<_A$. ⊗s is then $$(A_D_B_C)$. Also,
.begin nofill indent 16,16
⊗⊗topsort[$$((A.D) (B.D) (C.D) (C.A))$] = $$(B C A D)$⊗
⊗⊗topsort[$$((A.D) (B.D) (C.D) (C.A) (A.C))$] = $$(B)$⊗
.end
One method of producing such a ⊗u is to add elements to ⊗u one at a time.
At each stage choose any atom, ⊗x, occuring in ⊗po that is not already in
the chosen set and
which has no predecessors in ⊗po other than those already chosen. That is
any pair ⊗⊗y_._x⊗ that occurs in ⊗po is such that ⊗y is already chosen.
.break
Write a recursive function definition for ⊗topsort. Show that your
program is correct. That is, show that
the list returned by your program satisfies the conditions given above.
Your proof need not be formal, but it should be clear and well organized.
Try to make a simple statement of the correctness in terms of some well
chosen lemmas, such that the statement itself is fairly obvious. Then
fill in the details (proofs of lemmas) as much as you have time to.
You may want to put some effort into improving your program so that it is
easier to prove correct.
The desired list ⊗u is produced by ⊗ts1 applied to ⊗po and the
set ⊗⊗s_=_elements_po⊗ of elements of ⊗po. ⊗ts1 looks for an element, ⊗m, of
the remaining set ⊗s that has no predecessor in the remaining constraint ⊗po.
If it succeeds, ⊗m becomes the next element of the result and is ⊗⊗del⊗ed from
⊗s and ⊗⊗rem⊗ed from ⊗po. The process ⊗rem removes the restriction that
⊗m preceed any remaining element, as this is now guaranteed.
.begin nofill indent 12,12
⊗⊗ topsort po ← ts1[po, elements po]⊗
⊗⊗ ts1[po, s] ← ⊗
⊗⊗ {findmin[po, s]}[λm: ⊗
⊗⊗ qif m = $$NOMIN$ qthen qNIL⊗
⊗⊗ qelse m . ts1[rem[m, po], del[m, s]]]⊗
⊗⊗ findmin[po, s] ← ⊗
⊗⊗ qif qn s qthen $$NOMIN$⊗
⊗⊗ qelse qif nopred[qa s, po] qthen qa s⊗
⊗⊗ qelse findmin[po, qd s]⊗
⊗⊗ rem[x, po] ← ⊗
⊗⊗ qif qn po qthen qNIL⊗
⊗⊗ qelse qif x = qaa po qthen rem[x, qd po]⊗
⊗⊗ qelse qa po . rem[x, qd po]⊗
⊗⊗ nopred[x, po] ← qn po ∨ [¬[x = qda po] ∧ nopred[x, qd po]]⊗
⊗⊗ elements po ← el1[po, qNIL]⊗
⊗⊗ el1[po, s] ← qif qn po qthen s qelse el1[qd po, addpair[qa po, s]]⊗
⊗⊗ addpair[pr, s] ← ⊗
⊗⊗ qif memq[qa pr, s] qthen [qif memq[qd pr, s] qthen s qelse qd pr . s]⊗
⊗⊗ qelse qif memq[qd pr, s] qthen qa pr . s⊗
⊗⊗ qelse qa pr . [qd pr . s]⊗
.end
It is clear that ⊗ts1 returns a list ⊗u containing each element of ⊗s
at most once. Furthermore at any stage the result sofar plus the remains of ⊗s
add up to the original ⊗s. Thus when ⊗ts1 stops either ⊗s has been used up and
every element of ⊗s is contained in ⊗u exactly once, or every element of the
remaining ⊗s has a predecessor in the remaining ⊗po (hence in the initial ⊗po).
In this case in every ordering of the remaining elements some element will
follow some element it is required to preceed and it is impossible to sort all
of ⊗s. [eg. ⊗po does not define a partial-ordering]
To show that the list ⊗u produced by ⊗⊗ts1[po,s]⊗ satisfies the
ordering requirements we note that:
.begin nofill
⊗⊗findmin[po,s]≠$$NOMIN$ ⊃ nopred[findmin[po,s],po]⊗
thus we can show by induction on ⊗⊗length_s⊗ that ⊗⊗sorted[ts1[po,s],po]⊗, where
⊗⊗sorted[u,po]←qn u ∨ [nopred[qa u,po] ∧ sorted[qd u,rem[qa u,po]]]⊗
.end
Suppose ⊗sorted[u,po] is true and ⊗x.yεpo and ⊗y comes before ⊗x in ⊗u. Then
as ⊗u contains each element at most once, by ⊗⊗cdr⊗ing through ⊗u we will
arrive at a stage where ⊗sorted[u',po'] holds with ⊗⊗y_=_qa u⊗, ⊗⊗x_ε_qd u⊗,
and the ⊗⊗x.y_ε_po'⊗ as ⊗x will not have been ⊗⊗rem⊗ed from ⊗po. This
violates ⊗⊗nopred[qa u',po']⊗ and thus leads to a contradiction. Hence
the statement that ⊗⊗sorted[ts1[po,s],po]⊗ is sufficient to prove that
the ordering requirements are satisfied.
[25 points]#. Add a clause ⊗⊗qif qa exp = $WHILE qthen ... ⊗ to ⊗compexp in LCOM0
[or LCOM4]
to compile $WHILE expressions, and write the necessary auxiliary functions.
A $WHILE expression has the form $$(WHILE <exp> DO <stmts>)$ where
$<exp> can be any LISP term that LCOM0 is capable of compiling and $<stmts>
is a list of while-statements each of which is of one of the following forms:
$$(SETQ <var> <exp>)$, $$(RETURN <exp>)$ or $$(IF <exp> <stmt>)$ where
$<var> is a variable name, and the $<stmt> in the $IF is either a
$SETQ or a $RETURN statement, but not a conditional. The $WHILE expression
is evaluated as follows: first evaluate the $<exp>, and if it is qNIL
then the value of the whole expression is qNIL. Otherwise execute the
sequence of statements in order. If a $RETURN is executed then the value
of the $WHILE expression is the value of $<exp> in the $RETURN statement.
If a $SETQ is executed, the value of $<var> becomes the value of the
$<exp>. If and $IF is executed, the $<exp> is evaluated and if it is
not qNIL then the $<stmt> is executed, otherwise it has no effect.
If the end of the sequence is reached then repeat this process.
You may assume that any variables occuring in the $WHILE expression
are already bound and thus the relative stack position of the variable can
be obtained by adding the value of ⊗⊗qd assoc[var,vpr]⊗ to ⊗m, the basic
stack offset argument in ⊗compexp.
Thus after adding such a clause to LCOM4 we might have [after flattening]
.BEGIN NOFILL
⊗⊗compexp[$$(WHILE T DO ((IF (NULL U) (RETURN Z)) (SETQ Z (CONS (CAR U) Z))
(SETQ U (CDR U))))$,⊗
⊗⊗ -10,⊗
⊗⊗ $$((U.5) (Z.4))$] =⊗
.BEGIN INDENT 24,24
.SELECT 6
TAG0
(MOVEI 1 (QUOTE T))
(JUMPE 1 TAG1)
(MOVE 1 5 P)
(JUMPN 1 TAG2)
(MOVE 1 4 P)
(JRST 0 TAG1)
TAG2
(HLRZ 1 @ 5 P)
(MOVE 2 4 P)
(CALL 2 (QUOTE CONS))
(MOVEM 1 4 P)
(HRRZ 1 @ 5 P)
(MOVEM 1 5 P)
(JRST 0 TAG0)
TAG1
.END
.END
.begin nofill
The clause to add to ⊗compexp is:
⊗⊗ qelse qif qa exp = $$WHILE$ qthen compwhile[qad exp,qaddd exp,gensym[],gensym[],m,vpr]⊗
where
.indent 12,12
⊗⊗ compwhile[exp, seq, l1, l2, m, vpr] ← ⊗
⊗⊗ l1⊗
⊗⊗ . [combool[exp, m, l2, qNIL, vpr]⊗
⊗⊗ * [compseq[seq, l2, m, vpr] * <<$$JRST$, 0, l1>, l2>]]⊗
⊗⊗ compseq[seq, l, m, vpr] ← ⊗
⊗⊗ qif qn seq qthen qNIL⊗
⊗⊗ qelse comstmt[qa seq, l, m, vpr] * compseq[qd seq, l, m, vpr]⊗
⊗⊗ compstmt[stmt, l, m, vpr] ← ⊗
⊗⊗ qif qa stmt = $$SETQ$ qthen ⊗
⊗⊗ [compexp[qadd stmt, m, vpr]⊗
⊗⊗ * <<$$MOVEM$, 1, m + qd assoc[qad stmt, vpr], $$P$>>]⊗
⊗⊗ qelse qif qa stmt = $$RETURN$ qthen ⊗
⊗⊗ [compexp[qad stmt, m, vpr] * <<$$JRST$, 0, l>>]⊗
⊗⊗ qelse qif qa stmt = $$IF$ qthen ⊗
⊗⊗ {gensym[]}[λll: ⊗
⊗⊗ combool[qad stmt, m, ll, qNIL, vpr]⊗
⊗⊗ * [compstmt[qadd stmt, l, m, vpr] * <ll>]]⊗
.end